package com.cheung.leetcode.str;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

public class LC30 {


    public static List<Integer> findSubstring(String s, String[] words) {
        List<Integer> result = new ArrayList<>();
        // 单个字符串的长度
        int length = words[0].length();
        // 拼接字符串的长度
        int total = words.length * length;
        // 如果s的长度小于拼接后的字符串长度，直接返回空
        if (s.length() < total) {
            return result;
        }

        Map<String, Integer> hash = new HashMap<>();
        for (String word : words) {
            hash.put(word, hash.getOrDefault(word, 0) + 1);
        }

        for (int i = 0; i <= s.length() - total; i++) {
            Map<String, Integer> temp = new HashMap<>();
            // 待比较的子串
            String sub = s.substring(i, i + total);
            System.out.println("print:" + sub);
            int index = 0;
            while (index < total) {
                String substring = sub.substring(index, index + length);
                if (!hash.containsKey(substring) || temp.getOrDefault(substring, 0) >= hash.get(substring)) {
                    break;
                } else {
                    temp.put(substring, temp.getOrDefault(substring, 0) + 1);
                    index += length;
                }
            }
            if (index == total) {
                result.add(i);
            }

        }

        return result;
    }


    public static void main(String[] args) {
        String s = "wordgoodgoodgoodbestword";
        String[] words = {"word", "good", "best", "good"};
        System.out.println(findSubstring(s, words));


    }
}
